package _11_整理题目._2_二叉树_递归_dfs_bfs._递归;


import org.junit.Test;
import util.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 求给定二叉树的最大深度，
 * 最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。
 * 
 * 解法有两种：bfs，dfs
 * bfs：
 *      一层一层的看，统计一共有多少层，即最大的深度
 *      使用 Queue，之字形层级遍历 的写法，只不过最后返回的是 level
 * dfs：
 *      要计算 root 的最大深度，选出 子树 left right 的最大值 + 1 即可
 *      递归结束条件即 root==null  return 0;
 *
 *
 * 补充 二叉树的 bfs 和 dfs：
 * BFS：
 *      概念：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
 *      实现用到的数据结构：队列
 *      父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可
 * DFS
 *      概念：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。
 *      实现数据结构：栈
 *      父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可
 *      
 * bfs、dfs、前中后序遍历、层级遍历的关系
 *      bfd,dfs 是最基础的两种遍历思想
 *      前中后序遍历 其实暗含着 dfs 思想，可以使用 递归方法 实现
 *      单独的 dfs 可以使用 栈 实现
 *      层级遍历 就是 bfs 思想，可以使用 队列 实现
 *      
 */
public class _02_二叉树的最大深度 {
    
    public int dfs (TreeNode root) {
        if (root == null) return 0;

        int l = dfs(root.left);
        int r = dfs(root.right);

        return Math.max(l, r) + 1;
    }
    
    public int bfs(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        int level = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            level++;
        }
        return level;
    }

    @Test
    public void main() {
        Integer[] input = {1, 2, 3, 4, null, null, 5};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println("MaxDepth = " + dfs(root));
        System.out.println("MaxDepth = " + bfs(root));
    }
    
}
